package pers.qianyu.month_202103.date_20210330;

/**
 * 695. 岛屿的最大面积
 * https://leetcode-cn.com/problems/max-area-of-island/
 *
 * @author mizzle rain
 * @date 2021-03-30 17:04
 */
public class MaxAreaOfIsland {
    int[][] grid;

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        if (n == 0) return 0;
        this.grid = grid;

        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    boolean[][] visited = new boolean[m][n];
                    visited[i][j] = true;
                    res = Math.max(res, recur(i, j, visited));
                }
            }
        }
        return res;
    }

    private int recur(int i, int j, boolean[][] visited) {
        int[][] dxy = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        int m = grid.length, n = grid[0].length;

        int r = 1;
        for (int[] dis : dxy) {
            int x = i + dis[0], y = j + dis[1];
            if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] == 1 && !visited[x][y]) {
                visited[x][y] = true;
                r += recur(x, y, visited);
            }
        }
        return r;
    }
}
